﻿#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;


//给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
//请注意 ，必须在不复制数组的情况下原地对数组进行操作。
class Solution1 {
public:
	void moveZeroes(vector<int>& nums) {
		int begin = 0;
		int end = nums.size() - 1;
		int left = 0; int right = 0;
		while (begin<end)
		{
			while (begin<end&&nums[end] == 0)
			{
				end--;
			}
			while (begin<end&&nums[begin] != 0)
			{
				begin++;
			}
			//开始挪动数据
			if (begin<end)
			{
				left = begin;
				right = end;
				while (left<right)
				{
					swap(nums[left], nums[left + 1]);
					left++;
				}
			}
		}
	}
};

//改进
class Solution2{
public:
	void moveZeroes(vector<int>& nums) {
		for (int cur = 0, dest = -1; cur<nums.size(); cur++)//for这里同时定义两个的时候！！！！
		{
			if (nums[cur] != 0)
			{
				swap(nums[++dest], nums[cur]);
			}
		}
	}
};



//给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

class Solution3{
public:
	void duplicateZeros(vector<int>& arr) {
		vector<int >cpy;
		for (int i = 0; cpy.size() <= arr.size(); i++)
		{
			if (arr[i] == 0)
			{
				cpy.push_back(0);
				cpy.push_back(0);
			}
			else
			{
				cpy.push_back(arr[i]);
			}
		}
		// auto it=cpy.begin();
		// for(auto a:cpy)
		// {

		// }
		for (int i = 0; i<arr.size(); i++)
		{
			arr[i] = cpy[i];
		}
	}
};



class Solution4 {
public:
	void duplicateZeros(vector<int>& arr) {
		//找cur开始的位置
		int cur = 0;
		int dest = -1;
		int n = arr.size();
		while (dest<n - 1)
		{
			if (arr[cur] == 0)
			{
				dest += 2;
				cur++;
			}
			else
			{
				dest++;
				cur++;
			}

		}
		cur -= 1;
		while (cur >= 0)
		{
			if (dest == n)
			{
				arr[dest - 1] = 0;
				dest -= 2;

			}
			else
			{
				if (arr[cur] == 0)
				{
					arr[dest] = arr[dest - 1] = 0;
					dest -= 2;
				}
				else
				{
					arr[dest] = 0;
					dest--;

				}
			}
			cur--;
		}
	}
};
//编写一个算法来判断一个数 n 是不是快乐数。
//
//「快乐数」 定义为：
//
//对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
//然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
//如果这个过程 结果为 1，那么这个数就是快乐数。
//如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
class Solution5 {
public:
	int equa_add(int n) {
		int add = 0;
		while (n) {
			int a = n % 10;
			add += a * a;
			n /= 10;
		}
		return add;
	}
	bool isHappy(int n) {
		// 解决平方和
		int fast = n;
		int slow = n;
		while (1) {
			fast = equa_add(fast);
			fast = equa_add(fast);
			slow = equa_add(slow);
			if (fast == slow)
				break;


		}
		if (fast == 1)
			return true;
		else
			return
			false;
	}
};

//
//给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是(i, 0) 和(i, height[i]) 。
//
//找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
//
//返回容器可以储存的最大水量。
class Solution6 {
public:
	int maxArea(vector<int>& height) {
		int max = 0;
		int lenth = 0;
		int high = 0;
		for (int i = 0; i<height.size(); i++)
		{
			for (int j = i + 1; j<height.size(); j++)
			{
				//   if(max<((j-i)*(height[i]<height[j]?height[i]:height[j])) ) 
				//   max=((j-i)*(height[i]>height[j]?height[i]:height[j]));
				lenth = j - i;
				high = height[i]<height[j] ? height[i] : height[j];
				if (max<(lenth*high))
					max = lenth*high;
			}
		}
		return max;
	}
};//超出时间限制
class Solution7 {
public:
	int maxArea(vector<int>& height) {
		int max = 0;
		int left = 0;
		
		int right = height.size() - 1;
		int v = 0;
		while (left<right)
		{
			v = (right - left)*(height[right]<height[left] ? height[right] : height[left]);
			if (max<v)
				max = v;
			if (height[right]<height[left])
				right -= 1;
			else
				left += 1;
		}
		return max;
	}
};



//给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
class Solution8 {
public:
	int triangleNumber(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int times = 0;
		int left = 0;
		int right = 0;
		for (int i = nums.size() - 1; i > 1; i--) {
			left = 0;
			right = i - 1;
			while (right > left) {
				if ((nums[left] + nums[right]) > nums[i]) {
					times += right - left;
					right--;
				}
				else {
					left++;
				}
			}
		}
		return times;
	}
};



class Solution9 {
public:
	vector<int> twoSum(vector<int>& price, int target) {
		int left = 0;
		int right = price.size() - 1;
		vector<int> v;
		while (left<right)
		{
			if ((price[left] + price[right]) == target)
			{
				v.push_back(left);
				v.push_back(right);
				return v;
			}
			else{
				left++;
				right--;
			}
		}
		return v;//思路有问题，
	}
};
//购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。
class Solution10 {
public:
	vector<int> twoSum(vector<int>& price, int target) {
		// int left=0;
		// int right=price.size()-1;
		// vector<int> v;
		// while(left<right)
		// {
		//     if((price[left]+price[right])==target)
		//     {
		//         v.push_back(price[left]);
		//         v.push_back(price[right]);
		//         return v;
		//     }
		//     else{
		//         left++;
		//         right--;
		//     }
		// }
		// return v;笑死了做题前看清题目好不好
		int left = 0;
		int right = price.size() - 1;
		vector<int> v;
		while (left<right)
		{
			if (price[left] + price[right]>target)
				right--;
			else if (price[left] + price[right]<target)
				left++;
			else
			{
				v.push_back(price[left]);
				v.push_back(price[right]);
				return v;
			}
		}
		return v;
	}
};

//给你一个整数数组 nums ，判断是否存在三元组[nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
//
//你返回所有和为 0 且不重复的三元组。
class Solution11 {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		//判断三数之和是否为0
		vector<vector<int>> vv;
		sort(nums.begin(), nums.end());
		// set<vector<int>> s1;
		int left = 0;
		int right = 0;
		for (int i = nums.size() - 1; i>1; i--)
		{
			right = i - 1;
			left = 0;
			while (right>left)
			{
				if (nums[left] + nums[right]>-nums[i])
				{
					right--;
				}
				else if (nums[left] + nums[right]<-nums[i])
				{
					left++;
				}
				else
				{
					vector<int >v;
					v.push_back(nums[left]);
					v.push_back(nums[right]);
					v.push_back(nums[i]);
					// s1.insert(v);
					vv.push_back(v);
					while (right>left&&nums[left] == nums[left + 1])
					{
						left++;
					}
					while (right>left&&nums[right] == nums[right - 1])
					{
						right--;
					}
					left++;
					right--;



				}
			}
			while (i>1 && nums[i] == nums[i - 1])
			{
				i--;
			}

		}
		//  vector<vector<int>> vv(s1.begin(),s1.end());
		return vv;
	}
};


class Solution12 {
public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
		sort(nums.begin(), nums.end());
		vector<vector<int>> vv;
		int right = 0;
		int left = 0;
		for (int i = 0; i<nums.size();)
		{
			for (int j = i + 1; j<nums.size();)
			{
				left = j + 1;
				right = nums.size() - 1;
				long long aims = (-((long long)nums[i] + nums[j]) + target);
				while (left<right)
				{
					if (aims>(nums[right] + nums[left]))
						left++;
					else if (aims<(nums[right] + nums[left]))
						right--;
					else
					{
						vv.push_back({ nums[i], nums[j], nums[left], nums[right] });
						while (left<right&&nums[left] == nums[left + 1])
						{
							left++;
						}
						while (left<right&&nums[right] == nums[right - 1])
						{
							right--;
						}
						left++;
						right--;

					}
				}
				while (j<nums.size() - 1 && nums[j] == nums[j + 1])
				{
					j++;
				}
				j++;
			}
			while (i<nums.size() - 1 && nums[i] == nums[i + 1])
			{
				i++;
			}
			i++;
		}
		return vv;
	}
};


class Solution13 {
public:
	int minSubArrayLen(int target, vector<int>& nums) {
		int right = 0;
		int left = 0;
		for (int i = 1; i <= nums.size(); i++) // 不同的宽度
		{
			right = left + i - 1;
			if (i ==2)
			{
				int b = 0;
			}
			while (right < nums.size()) {
				if (right == 4)
				{
					int a=0;
				}
				int sum = 0;
				int cur = left;
				while (cur <= right)
				{
					sum += nums[cur];
					cur++;
				}
				if (sum == target)
					return (right - left + 1);
				else
				{
					left++;
					right++;
				}
			}
		}
		return 0;
	}
};
class Solution14 {
public:
	int minSubArrayLen(int target, vector<int>& nums) {
		int right = 0;
		int left = 0;
		int sum = 0;
		int minlen = INT_MAX;
		bool flag = 0;
		while (right < nums.size()) {
			sum += nums[right];

			// while (left <= right) {
			//     if (sum >= target) {
			//         if (minlen > (right - left + 1))
			//             {
			//                 flag=1;
			//                 minlen = right - left;
			//             }

			//         sum -= nums[left];

			//         left++;
			//     }
			//     else
			//     break;
			// }
			while (left <= right) {
				if (sum >= target) {
					if (minlen > (right - left + 1)) {
						flag = 1;
						minlen = right - left + 1;
					}
					left++;
					sum -= nums[left - 1];
				}
				else {

					break;
				}
			}
			right++;
		}
		if (flag == 0) {
			return 0;
		}
		else
			return minlen;

		// for (int i = 1; i <= nums.size(); i++) // 不同的宽度
		// {
		//     left=0;
		//     right=left+i-1;

		//     while (right < nums.size()) {
		//         int sum=0;
		//         int cur=left;
		//         while(cur<=right)
		//         {
		//             sum+=nums[cur];
		//             cur++;
		//         }
		//         if(sum>=target)
		//         return i;
		//         else
		//         {
		//             left++;
		//             right++;
		//         }
		//     }
		// }
		//
	}
};
// class Solution
// {
// public:
//  int minSubArrayLen(int target, vector<int>& nums)
//  {
//  int n = nums.size(), sum = 0, len = INT_MAX;
//  for(int left = 0, right = 0; right < n; right++)
//  {
//  sum += nums[right]; // 进窗⼝
//  while(sum >= target) // 判断
//  {
//  len = min(len, right - left + 1); // 更新结果
//  sum -= nums[left++]; // 出窗⼝
//  }
//  }
//  return len == INT_MAX ? 0 : len;
//  }
// };


class Solution15 {
public:
	int find_common(string s, int left, int right) {
		// 挨个域left--》right-1；
		int cur = left;
		while (cur < right) {
			if (s[right] == s[cur] ) {
				return cur;
			}
			cur++;
		}
		return -1;
	}
	int lengthOfLongestSubstring(string s) {
		int left = 0;
		int right = 0;
		int max_len = INT_MIN;
		while (right<s.size() - 1)
		{
			right++;
			if (right == 3)
			{
				int a = 0;
			}
			int postion = find_common(s, left, right);
			if (postion == -1)
			{
				if (max_len<(right - left ))
					max_len = (right - left );

			}
			else
			{
				left = postion + 1;
			}
		}
		return max_len;
	}
};




class Solution16 {
public:
	int longestOnes(vector<int>& nums, int k) {
		int arr[2] = { 0 }; // 充当哈希表
		int left = 0;
		int right = 0;
		int lenth = INT_MIN;
		while (right<nums.size()) {
			arr[nums[right]]++;
			while (left <= right) {
				if (arr[0] > k) {
					// 所以在这个地方，用滑动窗口的思想来考虑，就是那个模板，会让思路更清楚
					arr[nums[left]]--;
					left++;
				}
				else
				{
					break;
				}
			}
			if (lenth<(left - right + 1))//这里写反了
			{
				lenth = (left - right + 1);
			}
			right++;

		}
		return lenth;
	}
};



class Solution17 {
public:
	int minOperations(vector<int>& nums, int x) {
		if (nums.empty())
			return-1;
		int left = 0;
		int right = 0;
		int comp_sum = 0;
		int sum = 0;
		int lenth = INT_MIN;
		for (auto e : nums) {
			comp_sum += e;
		}
		if (comp_sum == x)
			return nums.size();
		comp_sum -= x;
		while (right < nums.size()) {
			if (nums[right] == 20)
			{
				int a = 0;
			}
			sum += nums[right];
			while (left <= right) {
				if (sum == comp_sum) {
					if (lenth < (right - left + 1))
						lenth = (right - left + 1);
					/*sum -= nums[left];
					left++;*/
					break;
				}
				else if (sum > comp_sum) {
					sum -= nums[left];
					left++;
				}
				else
					break;
			}
			right++;
		}
		return lenth == INT_MIN ? -1 : (nums.size() - (right - left + 1));//这里你是啥意思肯定得换成lenth呀

		// while (left < right) {
		//     sum += nums[left];
		//     if (sum > x) {
		//         if (left != 0) {
		//             sum -= nums[left];
		//             left--;
		//         }

		//         break;
		//     }

		//     else if (sum == x)
		//         return left + 1;

		//     left++;
		// }
		// while (right > left) {
		//     sum += nums[right];
		//     while (left >= 0) {
		//         if (sum > x) {
		//             sum -= nums[left];
		//             left--;

		//         } else if (sum == x)
		//             return left+1+nums.size()-right;
		//             break;
		//     }
		//     if(sum>x)
		//     {
		//         return -1;
		//     }
		//     else if(sum==x)
		//     return nums.size()-right;

		// right--;
		// }
		// return
		// -1;//很明显你正着去找，情况会很复杂，为啥不反着来呢------》正难则反
	}
};



class Solution18 {
public:
	//int totalFruit(vector<int>& fruits) {
	//	// 关键就是记录树的种类
	//	map<int, int> s1;
	//	int right = 0;
	//	int left = 0;
	//	int lenth = INT_MIN;
	//	while (right < fruits.size()) {
	//		s1[fruits[right]]++;
	//		while (left <= right) {
	//			if (s1.size() > 2) {
	//				if (lenth < (right - left)) {
	//					lenth = (right - left);

	//				}
	//				while (s1[fruits[left]] != 1)
	//				{
	//					s1[fruits[left]]--;
	//					left++;
	//				}
	//				s1.erase(fruits[left]);
	//				left++;




	//			}
	//			else
	//				break;


	//		}
	//		right++;
	//	}
	//	return lenth;
	//}
	int totalFruit(vector<int>& fruits) {
		// 关键就是记录树的种类
		map<int, int> s1;
		int right = 0;
		int left = 0;
		int lenth = INT_MIN;
		while (right < fruits.size()) {
			s1[fruits[right]]++;
			while (left <= right) {
				if (s1.size() > 2) {
					if (lenth < (right - left)) {
						lenth = (right - left);
					}
					while (s1[fruits[left]] != 1) {
						s1[fruits[left]]--;
						left++;
					}
					s1.erase(fruits[left]);
					left++;

				}
				else
					break;
			}
			right++;
		}
		if (lenth < (right - left)) {
			lenth = (right - left);
		}
		return lenth == INT_MIN ? fruits.size() : lenth;
	}
};


class Solution19 {
public:
	bool find_common(int* p1, int* p2) {
		for (int i = 0; i < 128; i++) {
			if (p1[i] != p2[i])
				return false;
		}
		return true;
	}
	vector<int> findSubstring(string s, vector<string>& words) {
		int s_arr[128] = { 0 };
		int word_arr[128] = { 0 };
		int left = 0;
		int right = 0;
		int lenth = 0;
		int size = 0;
		vector<int> v;
		for (auto e : words) {
			for (auto b : e) {
				word_arr[b]++;
				size++;
			}
		}
		while (right < s.size()) {
			s_arr[s[right]]++;
			lenth++;
			if (lenth == size) {
				while (right < s.size()) {
					if (find_common(s_arr, word_arr)) {
						v.push_back(left);

					}
					s_arr[s[left]]--;
					left++;
					right++;
					s_arr[s[right]]++;
				}
			}
			else
			{
				right++;
			}
		}
		return v;
	}
};
class Solution20 {
public:
	bool is_common(int*p1, int*p2)
	{
		for (int i = 0; i<26; i++)
		{
			if (p1[i] != p2[i])
				return false;


		}
		return true;
	}
	vector<int> findAnagrams(string s, string p) {
		int left = 0;
		int right = 0;
		int count = 0;
		int p_arr[26] = { 0 };
		int s_arr[26] = { 0 };
		vector<int> v;
		for (auto e : p)
		{
			p_arr[e - 'a']++;
		}

		while (right<s.size())
		{
			if (right == 2)
			{
				int a = 0;
			}
			s_arr[s[right] - 'a']++;
			if ((p_arr[s[right] - 'a']>0) && (s_arr[s[right] - 'a']<p_arr[s[right] - 'a']))
				count++;
			if (right - left + 1>p.size())
			{
				if (p_arr[s[left] - 'a']>0 && s_arr[s[left] - 'a'] <= p_arr[s[left] - 'a'])
					count--;
				s_arr[s[left] - 'a']--;
				left++;
			}
			if (count == p.size() && is_common(p_arr, s_arr))
				v.push_back(left);

			right++;
		}
		return v;
	}
};


class Solution21 {
public:
	bool find_common(int* p1, int* p2) {
		for (int i = 0; i < 128; i++) {
			if (p1[i] != p2[i])
				return false;
		}
		return true;
	}
	vector<int> findSubstring(string s, vector<string>& words) {
		

		map<string, int> w_map;
		vector<int> v;
		int n = words[0].size();
		for (auto e : words) {
			w_map[e]++;
		}
		for (int i = 0; i < n;i++) {
			int left = i;
			int right = i;
			if (right == 0)
			{
				int a = 0;
			}

			int count = 0;
			map<string, int> s_map;

			while (right + n < s.size()) {
				string in = s.substr(right, n);
				s_map[in]++;
				if (s_map[in] <= w_map[in])
					count++;
				if (right - left + 1 > words.size() * n) {
					string out = s.substr(left, n);
					if (s_map[in] <= w_map[in])
						count--;
					s_map[out]--;
					left += n;
				}
				if (count == words.size())
					v.push_back(left);

				right += n;
			}
		}

		return v;
	}
};


class Solution22 {
public:
	int searchInsert(vector<int>& nums, int target) {
		//转化为找最右端点
		int left = 0;
		int right = nums.size()-1;
		int mid = 0;
		while (left<right)
		{
			mid = left + (right - left + 1) / 2;
			if (nums[mid] <= target)
			{
				left = mid;
			}
			else
			{
				right = mid - 1;
			}
		}
		if (nums[left] == target)
			return left;
		else
			return left + 1;
	}
};


class Solution23 {
public:
	int mySqrt(int x) {
		//题目就是这样，和今后在分析客户的要求的时候一样，先去了解这个示例的值可以怎么得到
		int left = 0;
		int right = x;//很关键的点---》right到底定位在哪里//
		int mid = 0;
		while (left<right)
		{
			mid = left + (right - left) / 2;
			if ((mid*mid) <= x)
			{
				left = mid;
			}
			else
			{
				right = mid - 1;
			}
		}
		return left;
	}
};


class Solution24 {
public:
	int peakIndexInMountainArray(vector<int>& arr) {
		int left = 0;
		int right = arr.size() - 1;
		int mid = 0;
		while (left<right)
		{
			mid = left + (right - left + 1) / 2;
			if (arr[mid] >= arr[mid - 1])
				left = mid;
			else
				right = mid - 1;
		}
		return left;
	}
};


class Solution25 {
public:
	int findPeakElement(vector<int>& nums) {
		int right = nums.size() - 1;
		int left = 0;
		int mid = 0;
		while (left<right)
		{
			mid = left + (right - left + 1) / 2;
			if (nums[mid] >= nums[mid - 1])
				left = mid;
			else
				right = mid - 1;
		}
		return left;
	}
};
int main()
{
	//Solution4 s;
	
	//Solution23 s;
	//
	//vector<int> v2 = { 1, 3, 5, 6 };
	//
	////1, 0, 2, 3, 0, 4, 5, 0
	///*v.push_back(3);
	//v.push_back(2);
	//v.push_back(20);
	//v.push_back(1);
	//v.push_back(1);
	//v.push_back(3);*/
	////s.searchInsert(v2, 5);
	//s.mySqrt(8);
	
	
		/*v2=s.twoSum(v, 18);*/

	return 0;
}